One of the key functionalities of network devices such as routers is to parse the headers and in some cases the payloads of data packets in order to obtain information necessary to route data packets across a network. This information, which may include transport protocols, port numbers and source and destination addresses, may be used to classify packets in order to assign certain actions or determine measurements on the data packets and their transmission. For example, the information may be used to provide differentiated services to customers by providing customizable performance or bandwidth in accordance with service agreements. The information may additionally or alternatively be used to limit access of unauthorized users to parts of the network or to drop and/or redirect data packets.
In some instances, access control lists (ACLs) may implement the complex policies and filtering rules necessary for the above process. The ACLs may be sequential in nature, with incoming packets being sequentially compared to a list of rules. Due to networking becoming more complex, the rules may be quite complex. As processors may need to literally compare each rule or set of fields (e.g., that form part of a lookup key) sequentially with a packet until a match is found, the classification performance may be highly dependent on the complexity and number of rules.
In many applications the lookup table (or lookup key size) is fixed, although the fields necessary for classification, as well as the size of each field for different protocol stacks, may differ. Also, in a typical ACL configuration many fields may not be relevant to the classification of the packet. For example, fields may be “don't care” or wildcard fields that need not be included in the lookup key or rule set.